#include <vector>
#include <functional>

using namespace std;

// 704. 二分查找
class Solution1
{
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }

        return -1;
    }
};

// LCR 106. 判断二分图
class Solution2
{
public:
    bool isBipartite(vector<vector<int>>& graph) 
    {
        int n = graph.size();
        vector<int> color(n);
        function<bool(int, int)> dfs = [&](int x, int flag)
        {
            color[x] = flag;
            for(int y : graph[x])
            {
                if(color[y] == 0 && !dfs(y, 3 - flag)) return false;
                else if(color[y] == flag) return false;
            }

            return true;
        };

        for(int i = 0; i < n; ++i)
        {
            if(color[i] == 0 && !dfs(i, 1)) return false;
        }
        return true;
    }
};

// 34. 在排序数组中查找元素的第一个和最后一个位置
class Solution3
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int n = nums.size();
        if(n == 0) return {-1, -1};

        int left = 0, right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        if(nums[left] != target) return {-1, -1};

        int begin = left;
        right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }

        return {begin, right};
    }
};

// LCR 068. 搜索插入位置
class Solution4
{
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        if(nums[left] < target) return left + 1;
        else return left;
    }
};

// LCR 072. x 的平方根
class Solution5
{
public:
    int mySqrt(int x) 
    {
        if(x < 1) return 0;

        long long left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left) / 2;
            if(mid * mid < x) left = mid + 1;
            else right = mid;
        }
        if(left * left == x) return left;
        else return left - 1;
    }
};

// LCR 069. 山脉数组的峰顶索引
class Solution6
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left = 1, right = arr.size() - 2;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] < arr[mid - 1]) right = mid - 1;
            else left = mid;
        }
        return left;
    }
};

// LCR 012. 寻找数组的中心下标
class Solution7
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size(), sum = 0;
        for(int x : nums) sum += x;

        int leftSum = 0;
        for(int i = 0; i < n; ++i)
        {
            if(leftSum == sum - nums[i] - leftSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }
};

// 1901. 寻找峰值 II
class Solution8
{
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) 
    {
        int m = mat.size(), n = mat[0].size();
        auto getMaxIndex = [&](int row)
        {
            int index = 0, maxNum = 0;
            for(int i = 0; i < n; ++i)
            {
                if(mat[row][i] > maxNum)
                {
                    maxNum = mat[row][i];
                    index = i;
                }
            }            
            return index;
        };

        int low = 0, high = m - 1, maxIndex = 0;
        while(low < high)
        {
            int mid = low + (high - low + 1) / 2;
            maxIndex = getMaxIndex(mid); // 找出 mid 行中的最大值
            // 找出 maxIndex 列中的峰值
            if(mat[mid][maxIndex] < mat[mid - 1][maxIndex]) high = mid - 1;
            else low = mid;
        }

        // low 行是 maxIndex 列中的峰值
        // 找到 low 行中的最大值
        maxIndex = getMaxIndex(low);
        return {low, maxIndex};
    }
};